package seteam12;

import java.util.ArrayList;

public class BackTrackingSolver implements Solver {

    @Override
    public boolean solve(SudokuBoard board) {
	// initialize
	int[][] boardGrid = board.getValues(); // TODO hard copy needed?

	ArrayList<Integer[]> unsolvedCells = new ArrayList<Integer[]>();
	for (int line = 0; line < boardGrid.length; line++) {
	    for (int column = 0; column < boardGrid[line].length; column++) {
		if (boardGrid[line][column] == 0) {
		    Integer[] cellPos = new Integer[2];
		    cellPos[0] = line;
		    cellPos[1] = column;
		    unsolvedCells.add(cellPos);
		}
	    }
	}

	@SuppressWarnings("unchecked")
	// java got a problem with generics and arrays
	ArrayList<Integer>[] candidates = (new ArrayList[unsolvedCells.size()]);
	for (int i = 0; i < unsolvedCells.size(); i++) {
	    candidates[i] = getCandidates(boardGrid, unsolvedCells.get(i)[0],
		    unsolvedCells.get(i)[1]);
	}

	// solve
	int curCell = 0;
	while (true) {
	    // check if the current cell has no candidates left
	    if (candidates[curCell].size() == 0) {
		if (curCell == 0) {
		    // if the first cell has no candidates left the sudoku can't
		    // be solved
		    return false;
		} else {
		    // backtracking: go back a cell and remove the tried
		    // candidate
		    candidates[--curCell].remove(0);
		    boardGrid[unsolvedCells.get(curCell)[0]][unsolvedCells
			    .get(curCell)[1]] = 0;
		}
	    } else {
		// plug in first candidate of current cell
		boardGrid[unsolvedCells.get(curCell)[0]][unsolvedCells
			.get(curCell)[1]] = candidates[curCell].get(0);
		// go on to the next cell and compute its new candidate list
		if (++curCell == unsolvedCells.size()) {
		    break; // last cell was filled
		}
		candidates[curCell] = getCandidates(boardGrid,
			unsolvedCells.get(curCell)[0],
			unsolvedCells.get(curCell)[1]);
	    }
	}
	board.setValues(boardGrid);
	return true;
    }

    /**
     * Computes possible candidates for the cell
     * 
     * @param line
     * @param column
     * @return candidate list
     */
    private ArrayList<Integer> getCandidates(int[][] board, int line, int column) {
	// assume 1-9 are candidates. then check the cell's line, column and box
	// and remove candidates as necessary
	ArrayList<Integer> candidates = new ArrayList<Integer>();
	for (int i = 1; i <= 9; i++) {
	    candidates.add(i);
	}

	// check line
	for (int l = 0; l < board.length; l++) {
	    candidates.remove((Integer) board[l][column]);
	}

	// check column
	for (int c = 0; c < board[line].length; c++) {
	    candidates.remove((Integer) board[line][c]);
	}

	assert Math.sqrt(board.length) * Math.sqrt(board.length) == board.length : "Size is no quadratic number.";
	int boxSize = Double.valueOf(Math.sqrt(board.length)).intValue();
	// start coordinates of box
	int boxLine = line - line % boxSize;
	int boxColumn = column - column % boxSize;
	// check box
	for (int l = boxLine; l < boxLine + boxSize; l++) {
	    for (int c = boxColumn; c < boxColumn + boxSize; c++) {
		candidates.remove((Integer) board[l][c]);
	    }
	}

	// // print candidate list
	// System.out.print(line + "x" + column + ": ");
	// for (int i = 0; i < candidates.size(); i++) {
	// System.out.print(candidates.get(i) + " ");
	// }
	// System.out.print("\n");

	return candidates;
    }
}
